chail Blog

[ICPC 2026 Wuhan I] Prime Game 博弈

· 3 分钟阅读· 本文阅读 – 次算法足迹
目录

题目描述

彩叶和辉夜最近迷上了一个基于质数的博弈游戏。

起初，她们共有一个正整数 nn。两人将轮流进行操作，彩叶与辉夜各完成一次操作视为一个回合。在每一个回合中：

  1. 彩叶先手：她需要选择一个非负整数 xx（0≤x<n0 \le x<n），并将当前的 nn 替换为 n+xn+x。
  2. 辉夜后手：她需要选择一个能整除当前 nn 的质数 pp（即 p∣np\mid n），并将当前的 nn 替换为 np\frac{n}{p}。

以上操作会不断重复，直到某个回合结束后，若 n=1n=1，则游戏立即结束。

在游戏过程中，彩叶希望最大化游戏进行的总回合数，而辉夜希望最小化总回合数。假设双方都足够聪明并采取最优策略，请你求出游戏最终会进行多少个回合。

输入格式

第一行包含一个整数 nn（1≤n≤10181 \le n \le 10^{18}），表示游戏初始的数字。

输出格式

输出一行包含一个整数，表示在双方都采取最优策略的情况下，游戏最终进行的总回合数。

输入输出样例 #1

输入 #1

1

输出 #1

0

输入输出样例 #2

输入 #2

9

输出 #2

4

输入输出样例 #3

输入 #3

16

输出 #3

5

题解

思考

可以发现当 n 为 、1、2 时游戏会在这一轮结束，其他情况彩叶可以把 n 变为合数使游戏继续。这里很容易想到结果和 n 的质因数有关。辉夜会使 n 和它质因数数量不断减少，而彩叶要使 n 尽可能大，质因数数量尽可能多。

那么彩叶就需要每次操作完 n 的最大质因子尽可能小，让下一轮的 n 尽可能大。2 是最小的质数，但有时凑不到 2 倍数的合数，可以凑到 3 倍数的。因此选择形如 2a⋅3b2^a·3^b 且除完最大质因数最大的那个数。

预处理出这些数及其结果，不断迭代计算即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    int n;
    cin >> n;
    vector<int> s,m;
    for (int u=1;u<=2ll*n;u*=3ll) {
        for (int v=u;v<=2ll*n;v*=2ll) {
            s.push_back(v);
        }
    }
    sort(s.begin(), s.end());
    for (int i:s) {
        if (i%3==0) m.push_back(i/3);
        else m.push_back(i/2);
    }
    int cnt = 0;
    while (n!=1) {
        cnt++;
        auto it = lower_bound(s.begin(), s.end(), n);

        int v = -1;
        for (;it!=s.end() && *it<n*2;++it) {
            if (m[it-s.begin()]>v) v = m[it-s.begin()];
        }
        n = v;
    }
    cout << cnt << "\n";
    return 0;
}

注意

// 生命如同戏剧，你永远预料不到转折出现在哪一篇章。
// 世间的奇遇之所以存在，就是为了给世人带来转机。